//题目:
// 给你一个链表数组，每个链表都已经按升序排列。
// 请你将所有链表合并到一个升序链表中，返回合并后的链表。

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
//代码：
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    struct cmp
    {
        bool operator()(ListNode* l1,ListNode* l2)
        {
            return l1->val>l2->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //法一（最优解）：
        // vector<int> vv;
        // for(auto list:lists){
        //     while(list)vv.push_back(list->val),list=list->next;
        // }
        // if(vv.size()==0)return nullptr;
        // //排序
        // sort(vv.begin(),vv.end());
        // //确定头结点
        // int i=0;
        // while(lists[i]==nullptr)i++;
        // ListNode* head=lists[i++];
        // //将所有的链表连接起来，即使上一个链表尾结点连接到下一个链表的头结点上
        // ListNode* prev_tail=head;
        // while(prev_tail->next) prev_tail=prev_tail->next;
        // for(;i<lists.size();i++){//从头结点的下一个节点开始
        //     if(prev_tail!=lists[i] && lists[i]!=nullptr)
        //     {
        //         prev_tail->next=lists[i];
        //         while(prev_tail->next)prev_tail=prev_tail->next;
        //     }
        // }
        // //将vv中的值重新插入链表中
        // prev_tail=head,i=0;
        // while(prev_tail){
        //     prev_tail->val=vv[i++];
        //     prev_tail=prev_tail->next;
        // }
        // //返回头结点
        // return head;

        //法二（小堆）：
        priority_queue<ListNode*,vector<ListNode*>,cmp> heap;//小堆，升序排序
        for(auto list:lists)
            if(list)heap.push(list);
        
        ListNode* head=new ListNode(0);
        ListNode* cur=head;
        while(!heap.empty()){
            cur->next=heap.top();
            heap.pop();
            //更新cur
            cur=cur->next;
            if(cur->next)heap.push(cur->next);
        }
        cur=head->next;
        delete head;
        return cur;
    }
};
